#include <stdio.h>
#include <memory.h>

int num[ 1001 ][ 1000 ];

int main( )
{
    int i, k[ 1001 ], n, j, t;
    memset( num, 0, sizeof( num ) );
    memset( k, 0, sizeof( k ) );
    num[ 1 ][ 0 ] = num[ 1 ][ 1 ] = 1;
    for ( i = 2; i <= 1000; i++ )
    {
        k[ i ] = k[ i - 1 ];
        for ( j = 0; j <= k[ i ]; j++ )
            num[ i ][ j ] = num[ i - 1 ][ j ] + num[ i - 2 ][ j ];
        for ( j = 0; j <= k[ i ]; j++ )
            if ( num[ i ][ j ] >= 10 )
            {
                if ( j == k[ i ] )
                {
                    k[ i ]++;
                    num[ i ][ j + 1 ] = num[ i ][ j ] / 10;
                    num[ i ][ j ] %= 10;
                }
                else
                {
                    num[ i ][ j + 1 ] += num[ i ][ j ] /10;
                    num[ i ][ j ] %= 10;
                }
            }
    }
    scanf("%d", &t);
    while ( t-- )
    {
        scanf("%d", &n);
        for ( i = k[ n ]; i >= 0; i-- )
            printf("%d", num[ n ][ i ]);
        printf("\n");
    }
    return 0;
}
